package graph.digraph;

import graph.weight.DirectedEdge;
import graph.weight.DirectedEdgeWeightedGraph;
import linear.Queue;
import priority.IndexMinPriorityQueue;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Dijkstra 算法 求加权有向 最短路径
 */
public class DijkstraSP {
    // 索引代表顶点，值表示从顶点s到当前顶点的最短路径上的最后一条边
    private DirectedEdge[] edgeTo;

    // 索引代表顶点，值从顶点s到当前顶点的最短路径的总权重
    private double[] distTo;

    // 存放树中顶点与非树中顶点之间的有效横切边
    private IndexMinPriorityQueue<Double> pq;

    // 根据一副加权有向图G和顶点s，创建一个计算顶点为s的最短路径树对象
    public DijkstraSP(DirectedEdgeWeightedGraph G, int s) {
        this.edgeTo = new DirectedEdge[G.V()];
        distTo = new double[G.V()];
        // 初始化
        for (int i = 0; i < G.V(); i++) {
            distTo[i] = Double.POSITIVE_INFINITY;
        }
        pq = new IndexMinPriorityQueue<>(G.V());
        // 类似 最小生成树 从s开始
        distTo[s] = 0.0;
        pq.insert(s, 0.0);

        while (!pq.isEmpty()) {
            relax(G, pq.delMin());
        }


    }

    /**
     * 松弛算法
     * 类似 primMst算法 遍历所有小边 并记录所有最小边 已经 s 到 其他所有顶点的最短路径 以及 权重
     */
    private void relax(DirectedEdgeWeightedGraph G, int v) {
        // 遍历 邻接表
        for (DirectedEdge e : G.adj(v)) {
            // 边终点
            int w = e.to();
            // 如果 s到w的距离（已记录的distTo[w]） 大于s到v到w (distTo[v]+e.weight()) 的距离 那就修改边
            if (distTo[w] > distTo[v] + e.weight()) {
                // 更新距离
                distTo[w] = distTo[v] + e.weight();
                // 更新边
                edgeTo[w] = e;

                if (pq.contains(w)) {
                    pq.changeItem(w, distTo[w]);
                } else {
                    pq.insert(w, distTo[w]);
                }
            }
        }
    }


    public double distTo(int v) {
        return distTo[v];
    }

    public boolean hasPathTo(int v) {
        return distTo[v] < Double.POSITIVE_INFINITY;
    }

    public Queue<DirectedEdge> pathTo(int v) {
        if (!hasPathTo(v)) {
            return null;
        }
        Queue<DirectedEdge> edges = new Queue<>();
        DirectedEdge e = null;
        while (true) {
            e = edgeTo[v];
            if (e == null) {
                break;
            }
            edges.enqueue(e);
            v = e.from();
        }
        return edges;
    }

    public static void main(String[] args) throws IOException {
        //创建输入流
        BufferedReader reader = new BufferedReader(new
                InputStreamReader(DijkstraSP.class.getClassLoader().getResourceAsStream("min_route_test.txt")));
        //读取顶点数目，初始化EdgeWeightedDigraph图
        int number = Integer.parseInt(reader.readLine());
        DirectedEdgeWeightedGraph G = new DirectedEdgeWeightedGraph(number);
        //读取边的数目
        int edgeNumber = Integer.parseInt(reader.readLine());
        //循环读取每一条边，并调用addEdge方法
        for (int i = 0; i < edgeNumber; i++) {
            String line = reader.readLine();
            int v = Integer.parseInt(line.split(" ")[0]);
            int w = Integer.parseInt(line.split(" ")[1]);
            double weight = Double.parseDouble(line.split(" ")[2]);
            G.addEdge(new DirectedEdge(v, w, weight));
        }
        //根据图G和顶点0，构建DijkstraSP对象
        DijkstraSP dsp = new DijkstraSP(G, 0);
//获取起点0到顶点6的最短路径
        Queue<DirectedEdge> edges = dsp.pathTo(6);
//打印输出
        for (DirectedEdge edge : edges) {
            System.out.println(edge.from() + "->" + edge.to() + "::" + edge.weight());
        }
    }

}
